// 2025/11/17
// 最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp;
        for(auto& num : nums)
        {
            if(dp.empty() || dp.back() < num)
                dp.push_back(num);
            else
            {
                int l = 0, r = dp.size() - 1, aim = r;
                while(l <= r)
                {
                    int mid = (l + r) >> 1;
                    if(dp[mid] >= num)
                    {
                        aim = mid;
                        r = mid - 1;
                    }
                    else
                    {
                        l = mid + 1;
                    }
                }
                dp[aim] = num;
            }
        }
        return dp.size();
    }
};